/**
 * 给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *
 * candidates中的每个数字在每个组合中只能使用一次。
 *
 * 注意：解集不能包含重复的组合。
 *
 *
 *题解：https://leetcode.cn/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
 */
class CombinationSum2 {
    List<List<Integer>> ret=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len=candidates.length;
        Deque<Integer> qu=new LinkedList<>();
        Arrays.sort(candidates);
        combinationSum2(candidates,target,qu,0,len);
        return ret;

    }
    public void combinationSum2(int[] candidates,int target,Deque<Integer> qu,int begin,int len){
        if(target==0){
            ret.add(new ArrayList<>(qu));
        }
        for(int i=begin;i<len;i++){
            if(target-candidates[i]<0){
                return;
            }
            if(i>begin&&candidates[i-1]==candidates[i]){
                continue;
            }
            qu.addLast(candidates[i]);
            combinationSum2(candidates,target-candidates[i],qu,i+1,len);
            qu.removeLast();
        }
    }
}